// BubbleSortRecursive.cpp

/*
对于冒泡排序来说，不仅可以通过上面那种非递归的方式来实现，也可以通过递归的方法来实现，例如：

```cpp
// 对于数组 {4, 9, 1, 5, 6} 来说，
//
// 第一次交换完后
// {4, 1, 5, 6, 9}
// 此时，9 的位置就确定了，我们只需要对 {4, 1, 5, 6} 这个子数组重新执行冒泡排序的过程
//
// 第二次交换完后
// {1, 4, 5, 6, 9}
// 此时，6 和 9 的位置就确定了，我们只需要对 {1, 4, 5} 这个子数组重新执行冒泡排序的过程
//
// 重复这个过程，直到子数组中只有一个数字为止，因为一个数字的数组默认就是已经排序好的了。
//
// 参考上面的注释提示，用递归的方式，实现冒泡排序
vector<int> bubbleSort(vector<int> array) {

}
*/

/*
             v lastPos == 0
{1, 4, 5, 6，9}
          ^i ^i+1       
*/

#include <iostream>
#include <vector>

using namespace std;

vector<int> bubbleSortRecursive(vector<int> array, int lastPos) {
  if (lastPos == 0) {
    return array;
  }

  // 比较并且交换
  for (int i = 0; i < lastPos; ++i) {
    if (array[i] > array[i + 1]) {
      swap(array[i], array[i + 1]);
    }
  }

  return bubbleSortRecursive(array, lastPos - 1);
}

vector<int> bubbleSort(vector<int> array) {
  return bubbleSortRecursive(array, array.size() - 1);
}



int main(int argc, char const *argv[])
{
  /* code */
  /* code */
  vector<int> array {4, 1, 5, 9, 6};
  
  array = bubbleSort(array);
  // bubbleSortRecursive(array, 4)
  // bubbleSortRecursive(array, 3)
  // bubbleSortRecursive(array, 2)
  // bubbleSortRecursive(array, 1)
  // bubbleSortRecursive(array, 0)

  for (int n : array) {
    cout<<n<<" ";
  }

  cout<<endl;
  return 0;
  return 0;
}
